//给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [5,7,9,8,3,2,4]
//输出：[5,9,7,4,2,3,8]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在 [0, 100] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/ 
//
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 395 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-05-01 14:32:06
 * @description LCR 144.翻转二叉树
 */
public class ErChaShuDeJingXiangLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ErChaShuDeJingXiangLcof fun=new ErChaShuDeJingXiangLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    /*递归实现，当为null返回   时间on,空间o h，h为高度，*/
    public TreeNode flipTree1(TreeNode root) {
		if(root==null) return root;
		TreeNode t=root.left;
		root.left=root.right;
		root.right=t;
		flipTree1(root.left);
		flipTree1(root.right);
		return root;
    }
    public TreeNode flipTree(TreeNode root) {
        if(root==null) return root;
        Deque<TreeNode> q=new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode node=q.poll();
            TreeNode left = node.left;
            node.left=node.right;
            node.right=left;
            if(node.left!=null)q.offer(node.left);
            if(node.right!=null)q.offer(node.right);

        }
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
